/*
 * BSTContruct.cpp
 *
 *  Created on: Aug 15, 2012
 *      Author: jh238d
 */

//Construct BT from In and preorder traversal.

#include "BSTNode.h"
#include <ext/hash_map>
#include <iostream>
#include <assert.h>
using namespace std;
using namespace __gnu_cxx;

typedef pair<int, int> p;
hash_map<int, int> m;

void map_to_index(int in[], int n){
	for(int i = 0; i< n; i++)
		m.insert(p(in[i], i));
}

BSTNode* BT_from_preorder_inorder_traversal(int pre[], int in[], int n, int offset){
	assert(n>=0);
	if(n==0) return NULL;
	int rootVal = pre[0];
	int i = m[pre[0]] - offset;
	BSTNode *root = new BSTNode();
	root->data = pre[0];
	cout << root->data << " ";
	root->left = BT_from_preorder_inorder_traversal(pre+1, in, i, offset);
	root->right = BT_from_preorder_inorder_traversal(pre+1+i, in+1+i, n-i-1, offset+i+1);
	return root;
}

/*int main(){
	int in[8] = {1,2,3,4,5,6,7,8};
	int pre[8] = {5,3,2,1,4,7,6,8};
	int n = sizeof(in)/sizeof(*in);
	map_to_index(in, n);
	BT_from_preorder_inorder_traversal(pre, in, n, 0);
	return 0;
}*/


